추천 시스템(recommender system)이란 사용자(user)가 상품(item)에 대해 어떻게 평가하는지를 예측하는 예측 시스템의 일종이다.
Amazon과 같은 인터넷 쇼핑 사이트나 Netflix 등의 온라인 비디오 콘텐츠 제공 사이트는 사용자가 각각의 상품에 대해 평가한 평점(rate)을 가지고 있다. 이 기록을 기반으로 해서 사용자가 아직 평가하지 않은 상품에 대한 점수를 예측함으로써 그 사용자에게 어떤 상품을 추천할 지 결정할 수 있다.
여기에서는 파이썬의 Surprise패키지를 사용하여 추천 시스템을 구현해 본다. Surprise 패키지는 Nicolas Hug 가 만든 오픈 소스 추천 시스템 패키지로 문서화가 잘 되어 있다,
Surprise 패키지는 다음 논문들을 기반으로 하여 작성되었으며 세부적인 파라미터 설정 및 수식은 논문 내용을 참고한다.
Koren2010: "Factor in the Neighbors: Scalable and Accurate Collaborative Filtering", YEHUDA KOREN. 2010
Koren2011: "Collaborative Filtering on Ordinal User Feedback", Yehuda Koren and Joseph Sill, 2011
Surprise 패키지는 콘솔에서 pip install surprise 명령으로 설치하거나 다음과 같이 github에서 repository를 clone하여 직접 설치한다. (SVD 모형은 최신 버전의 master branch에만 있으므로 git clone해야 사용할 수 있다.)
$ git clone https://github.com/NicolasHug/Surprise.git
$ cd Surprise
$ python setup.py install실습을 위해 다음과 같이 Surprise 패키지를 임포트한다.
In [1]:
import surprise
surprise 패키지에서는 MovieLense라는 영화 추천 웹사이트의 데이터를 샘플 평점 데이터로 제공한다. MovieLense 데이터 중 10만개의 샘플 데이터세트는 다음과 같이 로드한다.
In [2]:
data = surprise.Dataset.load_builtin('ml-100k')
이 데이터는 다음과 같이 데이터프레임으로 변환할 수 있다.
In [3]:
df = pd.DataFrame(data.raw_ratings, columns=["user", "item", "rate", "id"])
del df["id"]
df.head(10)
Out[3]:
여기에서 user 열은 사용자 아이디, item 열은 상품 아이디, rate 열은 평점이다. 즉, 196번 사용자는 242번 영화에 대해 평점 3점을 주었음을 알 수 있다.
이 데이터프레임에서 볼 수 있듯이
추천 시스템은 사용자 아이디와 상품 아이디라는 두 개의 카테고리 입력과 평점 출력을 가지는 예측 시스템
이다.
이 데이터를 다음과 같이 피봇테이블(pivot table) 형태로 만들면 x축이 상품, y축이 사용자 아이디인 평점 행렬(rate matrix) $R$ 이 된다.
평점 행렬 $R$의 행은 특정 사용자의 평점이고 평점 행렬 $R$의 열은 특정 상품의 평점이다.
In [4]:
df_table = df.set_index(["user", "item"]).unstack()
이 평점 행렬의 일부만 살펴보면 다음과 같이 평점 데이터가 일부 위치에만 존재하는 sparse 행렬임을 알 수 있다.
In [5]:
df_table.fillna("").ix[212:222, 808:817]
Out[5]:
평점 행렬의 빈칸을 흰색, 점수를 검은색으로 시각화 하면 다음과 같다.
In [6]:
plt.imshow(df_table)
plt.grid(False)
plt.xlabel("item")
plt.ylabel("user")
plt.title("Rate Matrix")
plt.show()
추천 시스템은 두 개의 카테고리 값 입력에서 하나의 실수 값 출력을 예측하는 회귀 모형이지만 여러가지 방법으로 예측 성능을 향상시키고 있다. 추천 시스템에서 사용되는 알고리즘은 다음과 같다.
베이스라인 모형(baseline model)은 사용자 아이디 $u$, 상품 아이디 $i$, 두 개의 카테고리 값 입력에서 평점 $r_{ui}$의 예측치 $\hat{r}_{ui}$ 을 예측하는 가장 단순한 모형으로 다음과 같이 사용자와 상품 특성에 의한 평균 평점의 합으로 나타난다.
$$ \hat{r}_{ui} = \mu + b_u + b_i $$이 식에서 $\mu$는 전체 평점의 평균이고, $b_u$는 동일한 사용자에 의한 평점 조정값, $b_i$는 동일한 상품에 대한 평점 조정값이다.
베이스라인 모형은 오차 함수를 최소화하도록 구해진다.
$$ \sum_{r_{ui} \in R_{train}} \left(r_{ui} - (\mu + b_u + b_i)\right)^2 $$여기에서 $R_{train}$는 트레이닝을 위한 데이터셋을 말한다.
과최적화를 피하기 위해 다음과 같이 정규화(regulaization) 항을 추가할 수 있다.
$$ \sum_{r_{ui} \in R_{train}} \left(r_{ui} - (\mu + b_u + b_i)\right)^2 + \lambda \left(b_u^2 + b_i^2 \right) $$surprise 패키지는 오차 함수를 최소화하기 위해 다음과 같은 두 가지 최적화 알고리즘을 제공한다. 알고리즘의 선택은 method 인수를 사용한다. 최적화 알고리즘에 따라 나머지 최적화 인수가 달라진다. 최적화 인수에 대한 자세한 설명은 Koren2010 논문을 참조한다.
reg_i: 상품에 대한 정규화 가중치. 디폴트는 10.reg_u: 사용자에 대한 정규화 가중치. 디폴트는 15.n_epochs: 최적화 반복 횟수. 디폴트는 10.reg: 정규화 가중치. 디폴트는 0.02.learning_rate: 최적화 스텝 사이즈. 디폴트는 0.005.n_epochs: 최적화 반복 횟수. 디폴트는 20.베이스라인 모형을 비롯한 surprise 패키지 모형을 사용하기 위해서는 다음과 같은 순서를 거친다.
split, folds 메소드를 사용하여 K-Fold 트레이닝 데이터셋과 테스트 데이터셋을 만든다.train 메서드와 트레이닝 데이터셋으로 모수를 추정한 후, test 메서드로 테스트 데이터셋에 대한 예측을 실시한다. accuracy 서브패키지의 성능평가 함수를 사용하여 예측 성능을 계산한다.이 과정은 evaluate 명령으로 단축할 수도 있다.
surprise 패키지는 베이스라인 모형을 위한 BaselineOnly 클래스를 제공한다.
우선 베이스라인 모형으로 다음과 같이 MovieLens 데이터를 처리해 보자. FCP(Fraction of Concordant Pairs)로 계산한 평가 점수는 약 0.70점이다.
In [7]:
data.split(n_folds=3)
bsl_options = {'method': 'als',
'n_epochs': 5,
'reg_u': 12,
'reg_i': 5
}
algo = surprise.BaselineOnly(bsl_options=bsl_options)
np.random.seed(0)
acc = np.zeros(3)
for i, (trainset, testset) in enumerate(data.folds()):
algo.train(trainset)
predictions = algo.test(testset)
acc[i] = surprise.accuracy.fcp(predictions, verbose=True)
acc.mean()
Out[7]:
accuracy 서브패키지에서는 다음과 같은 추천성능 평가기준을 제공한다.
이 식에서 $\hat{R}$은 테스트 데이터셋을 뜻한다.
MAE (Mean Absolute Error) $$ \text{MAE} = \frac{1}{|\hat{R}|} \sum_{\hat{r}_{ui} \in \hat{R}}|r_{ui} - \hat{r}_{ui}| $$
FCP (Fraction of Concordant Pairs)
위 평가기준 중에서 FCP는 Karen2011 에서 제안된 것으로 평점 자체가 아닌 평점에 의한 순위를 기준으로 하는 방법이다.
evaluate 명령을 사용하면 위 코드를 다음과 같이 짧게 만들면서 여러가지 평가기준을 사용할 수 있다.
In [8]:
surprise.evaluate(algo, data)
Out[8]:
CF(Collaborative Filter) 방법은 모든 사용자의 데이터를 균일하게 사용하는 것이 아니라 평점 행렬이 가진 특정한 패턴을 찾아서 이를 평점 예측에 사용하는 방법이다. CF 방법도 사용자나 상품 기준으로 평점의 유사성을 살피는 Neighborhood 모형과 행렬의 수치적 특징을 이용하는 Latent Factor 모형이 있다.
Neighborhood 모형은 Memory-based CF라고도 한다. 이 방법은 특정 사용자의 평점을 예측하기 위해 사용하는 것이아니라 해당 사용자와 유사한(similar) 사용자에 대해 가중치를 준다.
특히 해당 사용자와 유사한 사용자를 찾는 방법 즉, 평점 행렬에서 유사한 사용자 행 벡터를 찾아서 이를 기반으로 빈 데이터를 계산하는 방법을 사용자 기반 (User-based) CF라고 한다.
이와 달리 특정한 상품에 대해 사용자가 준 점수 즉, 평점 행렬의 상품 열 벡터의 유사성을 찾고 특정 상품과 유사한 평점 정보를 가지는 상품들로 해당 상품의 빈 데이터를 예측하는 방법을 상품 기반 (Item-based) CF라고 한다.
사용자 특성 벡터(평점 행렬의 행 벡터)이나 상품 특성 벡터(평점 행렬의 열 벡터)의 유사도(similarity)을 비교하기 위한 기준도 여러가지가 있을 수 있다.
surprise 패키지에서는 다음과 같은 유사도 기준을 제공한다.
일단 다음과 같이 msd(Mean Squared Difference)값을 계산한다. msd는 유클리드 공간에서의 거리 제곱에 비례하는 값이다.
유사도는 msd 값의 역수로 계산한다. 즉 거리가 멀수록 유사도는 떨어진다. msd값이 0이 되는 경우를 대비하여 1을 더해준다. $$ \begin{split}\text{msd_sim}(u, v) &= \frac{1}{\text{msd}(u, v) + 1}\\ \text{msd_sim}(i, j) &= \frac{1}{\text{msd}(i, j) + 1}\end{split} $$
코사인 유사도(Cosine Similarity)는 두 특성 벡터의 각도에 대한 코사인 값을 말한다. 벡터 $x$와 벡터 $y$ 사이의 각도 $\theta$ 는 두 벡터의 내적 $x \cdot y$와 다음과 같은 관계가 있다. 각도 $\theta$가 0도이면 코사인 유사도는 1이다. 반대로 각도 $\theta$가 90도이면 코사인 유사도는 0이다.
$$ x \cdot y = |x| |y| \cos\theta $$$$ \cos\theta = \dfrac{x \cdot y}{|x| |y|}$$피어슨 유사도는 두 벡터의 상관계수(Pearson correlation coefficient)를 말하며 다음과 같이 정의한다.
위 식에서 $\mu_u$는 사용자 $u$의 평균 평점이다.
위 식에서 $\mu_i$는 상품 $i$의 평균 평점이다.
상관계수는 가장 높은 경우의 값이 1이고 무상관인 경우에는 0이다.
피어슨-베이스라인 유사도는 피어슨-베이스라인 유사도와 같이 상관계수를 구하지만 각 벡터의 기댓값을 단순 평균이 아니라 베이스라인 모형에서 예측한 값을 사용한다.
피어슨-베이스라인 유사도는 벡터의 차원 즉, 두 사용자나 상품에 공통적으로 있는 평점 원소의 갯수를 이용하여 정규화를 하는 shrinkage를 추가하여 사용한다.
$$ \begin{split}\text{pearson_baseline_shrunk_sim}(u, v) &= \frac{|I_{uv}| - 1} {|I_{uv}| - 1 + \text{shrinkage}} \cdot \hat{\rho}_{uv}\end{split} $$$$ \begin{split}\text{pearson_baseline_shrunk_sim}(i, j) &= \frac{|U_{ij}| - 1} {|U_{ij}| - 1 + \text{shrinkage}} \cdot \hat{\rho}_{ij}\end{split} $$surprise 패키지의 유사도 설정 옵션은 다음과 같다.
name: 사용할 유사도의 종류를 나타내는 문자열. 디폴트는 'MSD'.user_based: True면 사용자 기반, False면 상품 기반.min_support: 두 사용자나, 상품에서 공통적으로 있는 평점 원소의 수의 최솟값. 공통 평점 원소의 수가 이 값보다 적으면 해당 벡터는 사용하지 않는다. 디폴트는 shrinkage: Shrinkage 가중치. 디폴트는 100.일단 유사도가 구해지면 평점을 예측하고자 하는 사용자(또는 상품)와 유사도가 큰 $k$개의 사용자(또는 상품) 벡터를 사용하여 가중 평균을 구해서 가중치를 예측한다. 이러한 방법을 KNN(K Nearest Neighbors) 기반 예측 방법이라고 한다.
surprise 패키지에서는 다음과 같은 3가지의 KNN 기반 가중치 예측 알고리즘 클래스를 제공한다.
KNNBasic또는 $$ \hat{r}_{ui} = \frac{ \sum\limits_{j \in N^k_u(i)} \text{sim}(i, j) \cdot r_{uj}} {\sum\limits_{j \in N^k_u(j)} \text{sim}(i, j)} $$
KNNWithMeans또는 $$ \hat{r}_{ui} = \mu_i + \frac{ \sum\limits_{j \in N^k_u(i)} \text{sim}(i, j) \cdot (r_{uj} - \mu_j)} {\sum\limits_{j \in N^k_u(i)} \text{sim}(i, j)} $$
KNNBaseline또는 $$ \hat{r}_{ui} = b_{ui} + \frac{ \sum\limits_{j \in N^k_u(i)} \text{sim}(i, j) \cdot (r_{uj} - b_{uj})} {\sum\limits_{j \in N^k_u(j)} \text{sim}(i, j)} $$
Neighborhood 모형을 사용하여 추천 시스템을 만들고 평가하는 코드는 아래와 같다.
In [9]:
sim_options = {'name': 'msd'}
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.evaluate(algo, data)
Out[9]:
In [10]:
sim_options = {'name': 'cosine'}
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.evaluate(algo, data)
Out[10]:
In [11]:
sim_options = {'name': 'pearson'}
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.evaluate(algo, data)
Out[11]:
In [12]:
sim_options = {'name': 'pearson_baseline'}
algo = surprise.KNNBasic(sim_options=sim_options)
surprise.evaluate(algo, data)
Out[12]:
In [13]:
sim_options = {'name': 'pearson_baseline'}
algo = surprise.KNNWithMeans(sim_options=sim_options)
surprise.evaluate(algo, data)
Out[13]:
In [14]:
sim_options = {'name': 'pearson_baseline'}
algo = surprise.KNNBaseline(sim_options=sim_options)
surprise.evaluate(algo, data)
Out[14]:
사용자의 특성 벡터나 상품의 특성 벡터의 길이는 수천에서 수십억에 달하는 긴 크기가 될 수도 있다.
Latent Factor 모형은 이렇게 긴 사용자 특성이나 상품 특성을 몇 개의 요인 벡터로 간략화(approximate)할 수 있다는 가정에서 출발한 모형이다.
PCA(Principle Component Analysis)를 사용하면 긴 특성 벡터를 소수의 차원으로 차원 축소할 수 있듯이 사용자의 특성도 차원 축소 할 수 있다.
영화에 대한 평점을 주는 경우, 코미디, 액션, 드라마 등 몇개의 장르 요인이 있어서 사용자는 특정한 장르 요소에 대해 더 점수를 많이 주거나 적게 줄 수 있다. 그리고 영화 자체도 이러한 장르 요인을 가지고 있다면 해당 사용자의 그 영화에 대한 평점은 사용자의 장르 요인 벡터와 영화의 장르 요인 벡터의 내적으로 표시할 수 있다.
예를 들어 액션을 싫어하고(-1) 코미디(2)나 드라마(3)를 좋아하는 사용자의 요인 벡터는 다음과 같다.
$$ p_u^T = (-1, 2, 3) $$어떤 영화가 액션 요소가 2이고 코미디 요소가 1이고, 드라마 요소가 1이라면
$$ q_i^T = (2, 1, 1) $$평점은 다음과 같을 것이다.
$$ r_{ui} = q_i^Tp_u = -1 \cdot 2 + 2 \cdot 1 + 3 \cdot 1 = 3$$Matrix Factorization 방법은 모든 사용자와 상품에 대해 다음 오차 함수를 최소화하는 요인 벡터를 찾아낸다. 즉 다음과 같은 행렬 $P$, $Q$를 찾는다.
$$ R \approx PQ^T $$여기에서
SVD (Singular Value Decomposition) 는 Matrix Factorization 문제를 푸는 방법 중 하나이다.
$m \times n$ 크기의 행렬 $R$은 다음과 같이 세 행렬의 곱으로 나타낼 수 있다. 이를 특이치 분해(Singular Value Decomposition) 라고 한닫.
$$ R = U \Sigma V^T $$이 식에서
$\Sigma$의 대각 성분은 특이치라고 하며 전체 특이치 중에서 가장 값이 큰 $k$개의 특이치만을 사용하여 (Truncated SVD), 다음과 같은 행렬을 만들수 있다.
이 행렬을 다시 조합하면 원래의 행렬과 같은 크기를 가지고 유사한 원소를 가지는 행렬을 만들 수 있다.
$$ \hat{U} \hat{\Sigma} \hat{V}^T = \hat{R} \approx R $$하지만 실제로 평점 행렬은 빈 원소가 많은 sparse 행렬로서 SVD를 바로 적용하기 힘들기 때문에 행렬 $P$, $Q$는 다음과 같은 모형에 대해 오차 함수를 최소화하여 구한다.
$$ \hat{r}_{ui} = \mu + b_u + b_i + q_i^Tp_u $$$$ \sum_{r_{ui} \in R_{train}} \left(r_{ui} - \hat{r}_{ui} \right)^2 + \lambda\left(b_i^2 + b_u^2 + ||q_i||^2 + ||p_u||^2\right) $$surprise 패키지에서는 matrix_factorization 서브패키지에서 SVD 와 SVDpp라는 클래스를 제공한다. 자세한 사용법은 다음 웹사이트를 참조한다.
In [15]:
algo = surprise.SVD(n_factors=200, n_epochs=30)
surprise.evaluate(algo, data)
Out[15]: